import { ArrUtil } from '../../arr'

/**
 * 将树形结构数组扁平化为一维数组的策略
 */
export const FlattenTreeStrategyConst = {
  DFS: 'DFS',
  BFS: 'BFS'
} as const

/**
 * 将树形结构数组扁平化为一维数组的策略的类型
 */
export type FlattenTreeStrategyConstType =
  (typeof FlattenTreeStrategyConst)[keyof typeof FlattenTreeStrategyConst]

/**
 * 将树形结构数组扁平化为一维数组的方法的配置选项参数类型
 */
export type FlattenTreeOptionsType = {
  childrenFieldName?: string
  isRemoveChildrenField?: boolean
  strategy?: FlattenTreeStrategyConstType
}

/**
 * 将树形结构数组扁平化为一维数组
 *
 * @param {Array<Record<string, any>>} arr 树形结构数组
 * @param {FlattenTreeOptionsType} options 将树形结构数组扁平化为一维数组的配置选项：
 * - childrenFieldName：树形结构数组中父节点中存放子节点的字段名，默认为 'children'
 * - isRemoveChildrenField：在将树形结构数组扁平化为一维数组的过程中，是否移除树形结构数组中
 * 父节点中存放子节点的字段，默认为 true
 * - strategy：扁平化数组过程中对树形结构数组的遍历策略，默认为 'DFS'，可选值有 'DFS' 和 'BFS'
 * @returns {Array<Record<string, any>>} 扁平化后的一维数组
 */
export const flattenTree = (
  arr: Array<Record<string, any>>,
  options: FlattenTreeOptionsType = {}
): Array<Record<string, any>> => {
  const { childrenFieldName, isRemoveChildrenField, strategy } = {
    childrenFieldName: 'children',
    isRemoveChildrenField: true,
    strategy: FlattenTreeStrategyConst.DFS,
    ...options
  }
  /**
   * 当前正在处理节点的处理函数：
   * - 备份当前节点的子节点
   * - 对当前正在处理的节点进行移除用于存放子节点字段的操作
   * - 将当前节点添加到结果数组中
   */
  const nodeHandler = (node: Record<string, any>) => {
    // 备份当前节点的子节点
    const children = node[childrenFieldName]
    // 如果要移除当前节点中用于存放子节点的字段，且当前节点存在用于存放子节点的字段
    if (isRemoveChildrenField && Reflect.has(node, childrenFieldName)) {
      Reflect.deleteProperty(node, childrenFieldName)
    }
    // 将当前节点添加到结果数组中
    result.push(node)
    return children
  }
  // 最终要返回的结果数组
  const result: Array<Record<string, any>> = []
  // 扁平化数组的策略为 DFS
  if (strategy === FlattenTreeStrategyConst.DFS) {
    const dfs = (node: Record<string, any>) => {
      // 处理当前节点
      const children = nodeHandler(node)
      // 如果当前节点存在子节点，则递归遍历子节点
      if (ArrUtil.isArr(children) && !ArrUtil.isEmpty(children)) {
        children.forEach(dfs)
      }
    }
    arr.forEach(dfs)
  }
  // 扁平化数组的策略为 BFS
  else {
    // 还未处理的节点队列
    const queue: Array<Record<string, any>> = [...arr]
    while (!ArrUtil.isEmpty(queue)) {
      const node = queue.shift()!
      // 处理当前节点
      const children = nodeHandler(node)
      // 如果当前节点存在子节点，则将子节点添加到队列中
      if (ArrUtil.isArr(children) && !ArrUtil.isEmpty(children)) {
        queue.push(...children)
      }
    }
  }
  return result
}

export type FlattenTreeType = typeof flattenTree
